package leetcode;


/**
 * @author Liangyaoyun
 */
public class KthLargestElementInArray {
    public void dualPivotQuickSort(int[] nums,int target) {
        dualPivotQuickSortInner(nums, 0, nums.length - 1,target);
    }
    private void dualPivotQuickSortInner(int[] nums, int start, int end,int  target) {

        if (end - start <= 0) {
            return;
        }

        int tmp;

        if (nums[start] > nums[end]) {
            tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
        }

        int pivot1 = nums[start];
        int pivot2 = nums[end];
        int lt = start + 1;
        int gt = end - 1;
        int i = start + 1;

        while (i <= gt) {
            if (nums[i] < pivot1) {
                tmp = nums[i];
                nums[i] = nums[lt];
                nums[lt] = tmp;
                i++;
                lt++;
            } else if (nums[i] >= pivot1 && nums[i] <= pivot2) {
                i++;
            } else {
                tmp = nums[i];
                nums[i] = nums[gt];
                nums[gt] = tmp;
                gt--;
            }
        }
        tmp = nums[start];
        nums[start] = nums[lt - 1];
        nums[lt - 1] = tmp;

        tmp = nums[end];
        nums[end] = nums[gt + 1];
        nums[gt + 1] = tmp;

        //如果目标值小于左轴，说明答案在左半部分
         if (nums[target]<nums[lt-1]){
            dualPivotQuickSortInner(nums, start, lt - 2,target);
        }
        //如果目标值大于左轴又小于右轴，则说明答案在中间部分
        else if (nums[target]>nums[lt-1]&&nums[target]<nums[gt+1]){
            dualPivotQuickSortInner(nums, lt, gt,target);
        }
        else {
            //如果目标值大于右轴，则说明答案在右半部分
            dualPivotQuickSortInner(nums, gt + 2, end, target);
        }

    }
    public int findKthLargest(int[] nums, int k) {
        int target=nums.length-k;
        dualPivotQuickSort(nums, target);
        return nums[target];
    }


}
